package problem873;

import java.util.HashMap;

//873.最长的斐波那契子序列
//https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        int n = arr.length;
        //存储数值和下标
        for(int i = 0; i<n; i++) {
            hash.put(arr[i], i);
        }
        int[][] dp = new int[n][n];
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                dp[i][j] = 2;
            }
        }

        // k i j
        int ret = 0;
        for(int j = 2; j<n; j++) {
            for(int i = j-1; i>0; i--) {
                int x = arr[j] - arr[i];
                if(hash.containsKey(x) && hash.get(x) < i) {
                    dp[i][j] = Math.max(dp[i][j], dp[hash.get(x)][i]+1);
                }
                ret = Math.max(ret, dp[i][j]);
            }
        }

        if(ret < 3) return 0;
        return ret;
    }
}

/*
dp[i][j]:以第i和j个数为结尾的最长斐波那契数列 i<j
k j i
*/